package com.leetcode.图.图的着色;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 给定无向连通图G和m种颜色。用这些颜色为G的各个顶点着色，每个顶点着一种颜色。 
 * 如果有一种色法使G的每条边的两个顶点着不同的颜色，则称这个图示m个着色的。
 * 图的m着色问题是对于给定图G和m种颜色，找出所有的不同的着色方法。
 * 
 * @author LZF
 *
 */
public class Main {
	public static int cnt = 0;
	public static Scanner input = new Scanner(System.in);
	public static void main(String[] args) {
		System.out.println("请输入顶点的个数和颜色的个数：");
		int N = input.nextInt();
		int m = input.nextInt();
		int[][] graph = new int[N][N];
		int[] result = new int[N];
		if(N > 1)
			System.out.println("请输入边（顶点从1开始，输入\"1 2\"表示顶点1和顶点2之间有边，输入\"0 0\"结束）");
		while(N > 1) {
			try {
				int i = input.nextInt();
				int j = input.nextInt();
				if(i == 0 && j == 0) break;
				if(i == j) continue;
				graph[i - 1][j - 1] = 1;
				graph[j - 1][i - 1] = 1;
			}catch(IndexOutOfBoundsException e){
				System.out.println("!!输入的顶点有误!!请输入顶点为1到" + N + "之间的整数!!");
			}
		}
		System.out.println("图的邻接矩阵如下：");
		printMetrix(graph);
//		int m = 1;
		while(true) {
			System.out.print("当颜色种数为 " + m + "时，");
			//第一个节点可以着1到m的颜色，开始深搜
			for(int c = 1;c <= m;c++) {
				result[0] = c;
				dfs(graph,1,result,m);
			}
			if(cnt == 0) {
				System.out.println("无法给图着色");
			}else {
				break;
			}
			m++;
		}
//		for(int c = 1;c <= m;c++) {
//			result[0] = c;
//			dfs(graph,1,result,m);
//		}
		System.out.println("总共有" + cnt + "种情况。");
		
	}
	/**
	 * 
	 * @param graph：图的邻接矩阵
	 * @param cur：指向当前的节点，判断可以着什么颜色
	 * @param result：存放每一种着色的情况
	 * @param m：总的颜色种数
	 */
	public static void dfs(int[][] graph,int cur,int[] result,int m) {
		//临界条件
		if(cur == graph.length) {
			//能走到这里，说明可以给图着色
			if(cnt == 0) {
				System.out.println("可以给图着色，如下：");
			}
			System.out.print(++cnt + ":");
			System.out.println(Arrays.toString(result));//输出结果情况
			return;
		}
		//遍历当前节点可以着的颜色
		for(int c = 1;c <= m;c++) {
			boolean flag = false;//判断当前颜色符不符合的标志
			for(int i = 0;i < cur;i++) {
				if(graph[cur][i] == 1 && c == result[i]) {
					flag = true;//表示该颜色在相邻的节点种已经用了
					break;
				}
			}
			if(flag) continue;//表示当前颜色不可以给这个节点着色
			result[cur] = c;//当前节点着上颜色c，继续深搜下一个节点
			dfs(graph,cur + 1,result,m);
		}
	}
	
	public static String arrToString(int[] a) {
		if (a == null)
            return "null";
        int iMax = a.length - 1;
        if (iMax == -1)
            return "数组为空";

        StringBuilder b = new StringBuilder();
        for (int i = 0; ; i++) {
            b.append(a[i]);
            if (i == iMax)
                return b.toString();
            b.append(" ");
        }
	}
	public static void printMetrix(int[][] a) {
		if(a.length == 0) System.out.println("矩阵为空");
		for(int i = 0;i < a.length;i++) {
			System.out.println(arrToString(a[i]));
		}
	}
}
